package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * 1080. 根到叶路径上的不足节点
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/25 20:52
 */
public class SufficientSubset {

    private int limit;

    public TreeNode sufficientSubset(TreeNode root, int limit) {
        this.limit = limit;
        sum(root, 0);
        boolean find = find(root);
        if (!find) {
            return null;
        }
        return root;
    }

    private boolean find(TreeNode node) {
        if (node.left == null && node.right == null) {
            return node.val != Integer.MIN_VALUE;
        }
        boolean a = false;
        boolean b = false;
        if (node.left != null) {
            a = find(node.left);
            if (!a) {
                node.left = null;
            }
        }
        if (node.right != null) {
            b = find(node.right);
            if (!b) {
                node.right = null;
            }
        }
        return a || b;
    }

    private void sum(TreeNode node, int s) {
        s += node.val;
        if (node.left == null && node.right == null) {
            if (s < limit) {
                node.val = Integer.MIN_VALUE;
            }
            return;
        }
        if (node.left != null) {
            sum(node.left, s);
        }
        if (node.right != null) {
            sum(node.right, s);
        }
    }

}
